package org.example.myleet.p825;

import java.util.Arrays;

public class Solution {
    public int numFriendRequests(int[] ages) {
        Arrays.sort(ages);
        int[] biggestIdx = new int[ages.length];
        biggestIdx[ages.length - 1] = ages.length - 1;
        for (int i = ages.length - 2; i >= 0; --i) {
            biggestIdx[i] = ages[i] == ages[i + 1] ? biggestIdx[i + 1] : i;
        }
        int sum = 0;
        for (int i = 0; i < ages.length; ++i) {
            int x = ages[i];
            int y = x / 2 + 7;
            if (y > x || y > ages[ages.length - 1]) {
                continue;
            }
            int l = 0, r = ages.length - 1;
            while (l < r) {
                int m = (l + r) >> 1;
                if (ages[m] > y) {
                    r = m;
                } else {
                    l = m + 1;
                }
            }
            if (ages[l] > 100 && x < 100) {
                continue;
            }
            sum += l <= biggestIdx[i] ? biggestIdx[i] - l : biggestIdx[i] - l + 1;
        }
        return sum;
    }
}
